#define _CRT_SECURE_NO_WARNINGS 1


class Solution {
public:
    vector<int> tmp;
    int mergesort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;

        int mid = (left + right) / 2;
        int l = mergesort(nums, left, mid);
        int r = mergesort(nums, mid + 1, right);

        int a = left, b = mid + 1, sum = 0;
        while (a <= mid)
        {
            while (b <= right && (long long)nums[a] <= 2 * (long long)nums[b]) b++;
            sum += right - b + 1;
            a++;
        }

        int i = left;
        a = left, b = mid + 1;
        while (a <= mid && b <= right) tmp[i++] = nums[a] > nums[b] ? nums[a++] : nums[b++];
        while (a <= mid) tmp[i++] = nums[a++];
        while (b <= right) tmp[i++] = nums[b++];
        for (int x = left; x <= right; x++) nums[x] = tmp[x];

        return l + r + sum;
    }

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergesort(nums, 0, nums.size() - 1);
    }
};